In
combinatorial mathematics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, a Levi graph or incidence graph is a
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
associated with an
incidence structure
In mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider the points and lines of the Euclidean plane as the two types of objects and ignore al ...
.
[. See in particula]
p. 181
From a collection of points and lines in an
incidence geometry
In mathematics, incidence geometry is the study of incidence structures. A geometric structure such as the Euclidean plane is a complicated object that involves concepts such as length, angles, continuity, betweenness, and incidence. An ''incide ...
or a
projective configuration
In mathematics, specifically projective geometry, a configuration in the plane consists of a finite set of points, and a finite arrangement of lines, such that each point is incident to the same number of lines and each line is incident to the ...
, we form a graph with one vertex per point, one vertex per line, and an edge for every incidence between a point and a line. They are named for
Friedrich Wilhelm Levi
Friedrich Wilhelm Daniel Levi (February 6, 1888 – January 1, 1966) was a German mathematician known for his work in abstract algebra, especially torsion-free abelian groups. He also worked in geometry, topology, set theory, and analysis.
Early ...
, who wrote about them in 1942.
The Levi graph of a system of points and lines usually has
girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
at least six: Any 4-
cycles would correspond to two lines through the same two points. Conversely any bipartite graph with girth at least six can be viewed as the Levi graph of an abstract incidence structure.
Levi graphs of configurations are
biregular, and every biregular graph with girth at least six can be viewed as the Levi graph of an abstract configuration.
[.]
Levi graphs may also be defined for other types of incidence structure, such as the incidences between points and planes in
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
. For every Levi graph, there is an equivalent
hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
, and vice versa.
Examples
* The
Desargues graph
In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level ...
is the Levi graph of the
Desargues configuration
In geometry, the Desargues configuration is a configuration of ten points and ten lines, with three points per line and three lines per point. It is named after Girard Desargues.
The Desargues configuration can be constructed in two dimensions f ...
, composed of 10 points and 10 lines. There are 3 points on each line, and 3 lines passing through each point. The Desargues graph can also be viewed as the
generalized Petersen graph
In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways ...
G(10,3) or the
bipartite Kneser graph with parameters 5,2. It is 3-regular with 20 vertices.
* The
Heawood graph Heawood is a surname. Notable people with the surname include:
* Jonathan Heawood, British journalist
*Percy John Heawood (1861–1955), British mathematician
**Heawood conjecture
** Heawood graph
**Heawood number In mathematics, the Heawood numbe ...
is the Levi graph of the
Fano plane
In finite geometry, the Fano plane (after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines c ...
. It is also known as the (3,6)-
cage
A cage is an enclosure often made of mesh, bars, or wires, used to confine, contain or protect something or someone. A cage can serve many purposes, including keeping an animal or person in captivity, capturing an animal or person, and displayin ...
, and is 3-regular with 14 vertices.
* The
Möbius–Kantor graph
In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen gra ...
is the Levi graph of the
Möbius–Kantor configuration
In geometry, the Möbius–Kantor configuration is a configuration consisting of eight points and eight lines, with three points on each line and three lines through each point. It is not possible to draw points and lines having this pattern of i ...
, a system of 8 points and 8 lines that cannot be realized by straight lines in the Euclidean plane. It is 3-regular with 16 vertices.
* The
Pappus graph
In the mathematical field of graph theory, the Pappus graph is a bipartite 3- regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek ...
is the Levi graph of the
Pappus configuration
In geometry, the Pappus configuration is a configuration of nine points and nine lines in the Euclidean plane, with three points per line and three lines through each point.
History and construction
This configuration is named after Pappus of ...
, composed of 9 points and 9 lines. Like the Desargues configuration there are 3 points on each line and 3 lines passing through each point. It is 3-regular with 18 vertices.
* The
Gray graph
Grey (more common in British English) or gray (more common in American English) is an intermediate color between black and white. It is a neutral or achromatic color, meaning literally that it is "without color", because it can be composed o ...
is the Levi graph of a configuration that can be realized in
as a
grid of 27 points and the 27 orthogonal lines through them.
* The
Tutte eight-cage
William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...
is the Levi graph of the
Cremona–Richmond configuration
In mathematics, the Cremona–Richmond configuration is a configuration of 15 lines and 15 points, having 3 points on each line and 3 lines through each point, and containing no triangles. It was studied by and . It is a generalized quadrangle wit ...
. It is also known as the (3,8)-cage, and is 3-regular with 30 vertices.
* The four-dimensional
hypercube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has vertices, ...
is the Levi graph of the
Möbius configuration
In geometry, the Möbius configuration or Möbius tetrads is a certain configuration in Euclidean space or projective space, consisting of two mutually inscribed tetrahedra: each vertex of one tetrahedron lies on a face plane of the other tetrahed ...
formed by the points and planes of two mutually incident tetrahedra.
* The
Ljubljana graph
In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges.
It is a cubic graph with diameter 8, radius 7, chromatic number 2 and chromatic index 3. Its girth is 10 and there ...
on 112 vertices is the Levi graph of the Ljubljana configuration.
[.]
References
External links
*
{{Incidence structures
Families of sets
Configurations (geometry)
Geometric graphs